package woa.binarysearch;

/**
 * 寻找两个正序数组的中位数
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 * 算法的时间复杂度应该为 O(log (m+n)) 。
 *
 * 输入：nums1 = [1,3], nums2 = [2]
 * 输出：2.00000
 * 解释：合并数组 = [1,2,3] ，中位数 2
 *
 * @author wangpeng
 * @date 2021/12/24
 */
public class FindMedianSortedArrays {

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length, len2 = nums2.length;
        int len = len1 + len2;
        //如果是奇数，则只需要找到len/2；如果是偶数，则需要找到(len/2 + len/2 - 1)/2
        boolean isOdd = len % 2 == 1;
        int k = len / 2 + 1;
        if (len1 == 0) {
            return isOdd ? nums2[k - 1] : (double) (nums2[k - 1] + nums2[k - 2]) / 2;
        }
        if (len2 == 0) {
            return isOdd ? nums1[k - 1] : (double) (nums1[k - 1] + nums1[k - 2]) / 2;
        }

        return isOdd ? getK(k, len1, len2, nums1, nums2) : (double) (getK(k, len1, len2, nums1, nums2) + getK(k - 1, len1, len2, nums1, nums2)) / 2;
    }

    public static int getK(int k, int len1, int len2, int[] nums1, int[] nums2) {
        int s1 = 0, s2 = 0;
        while (k > 1) {
            int mid = k / 2;
            if (len1 - s1 > 0 && len1 - s1 < mid) {
                mid = len1 - s1;
            } else if (len2 - s2 > 0 && len2 - s2 < mid) {
                mid = len2 - s2;
            }

            if (len2 - s2 == 0 || (len1 - s1 > 0 && nums1[s1 + mid - 1] < nums2[s2 + mid - 1])) {
                s1 = s1 + mid;
            } else {
                s2 = s2 + mid;
            }
            k = k - mid;
        }

        if (len2 - s2 == 0 || (len1 - s1 > 0 && nums1[s1] < nums2[s2])) {
            return nums1[s1];
        }

        return nums2[s2];
    }

    public static void main(String[] args) {
        System.out.println(findMedianSortedArrays(new int[]{}, new int[]{2,4,6,8}));
    }
}
